#ifndef MYBINARYTREE
#define MYBINARYTREE

#include <iostream>
#include <stack>

template <class T>
struct TreeNode
{
    T _data;
    TreeNode<T> *_left;
    TreeNode<T> *_right;
    TreeNode(const T &t = T())
        : _data(t), _left(nullptr), _right(nullptr)
    {
    }
};

template <class Node>
class BinaryTree
{
protected:
    Node *_root;
    // 递归遍历
    void _prevorder(Node *root)
    {
        if (root == nullptr)
            return;
        std::cout << root->data << " ";
        _prevorder(root->_left);
        _prevorder(root->_right);
    }
    void _inorder(Node *root)
    {
        if (root == nullptr)
            return;
        _inorder(root->_left);
        std::cout << root->data << " ";
        _inorder(root->_right);
    }
    void _postorder(Node *root)
    {
        // n0 = 60, n2 = 59, n = 119 <2^7-1 >2^6-1 = 2^h - 1
        if (root == nullptr)
            return;
        _postorder(root->_left);
        _postorder(root->_right);
        std::cout << root->data << " ";
    }

public:
    BinaryTree()
        : _root(nullptr)
    {
    }
    // 递归遍历
    void PrevOrder()
    {
        _prevorder(_root);
    }
    void InOrder()
    {
        _inorder(_root);
    }
    void PostOrder()
    {
        _postorder(_root);
    }

    //非递归遍历
    void NoRecursionPrevOrder()
    {
        if (_root) return;
        std::stack<Node *> st;
        st.push(_root);
        while (!st.empty())
        {
            Node *tmp = st.top();
            st.pop();
            std::cout << tmp->_data << " ";
            if (tmp->_right)
                st.push(tmp->_right);
            if (tmp->_left)
                st.push(tmp->_left);
        }
    }
    void NoRecursionInOrder()
    {
        if (_root) return;
        std::stack<Node *> st;
        st.push(_root);
        while (!st.empty())
        {
            if (tmp->_right)
                st.push(tmp->_right);
            Node *tmp = st.top();
            st.pop();
            std::cout << tmp->_data << " ";
            if (tmp->_left)
                st.push(tmp->_left);
        }
    }
    void NoRecursionPostOrder()
    {
        if (_root) return;
        std::stack<Node *> st;
        Node *cur = _root;
        Node *prev = nullptr;

    }
};

#endif